/**
 *  Bubble Sort
 * 
 *  
 *
 *  Time complexity: (n - 1) + (n - 2) + ... + 1 + 0 = n * (n - 1) / 2 = O(n^2) 
 *  Space complexity: O(1)
 *
 */

import java.util.Arrays;

class BubbleSort<E extends Comparable<E>> {

    public void sort(E[] a) {
        int N = a.length;
        for (int i = 0; i < N - 1; i++) { // Outter loop, each loop we put the largest number to the bottom (right)
            for (int j = 0; j < N - 1 - i; j++) { // Inner loop, compare a[j] and a[j + 1], swap them if a[j] > a[j + 1]
                if (a[j].compareTo(a[j + 1]) > 0) {
                    swap(a, j, j + 1);
                }
            }
        }
    }
    
    /**
     * Swap a[i] and a[j]
     *
     */
    private void swap(E[] a, int i, int j) {
        E tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}
